1. Field of the Invention
This invention is related to the art of searching for a desired bit string within a set of bit strings using a data configuration in the form of a tree that stores the bit strings.
2. Description of Related Art
In recent years, with advancements in information-based societies, large-scale databases have come to be used in various places. To search such large-scale databases, it is usual to search for a desired record, retrieving the desired record by using as indexes items within records associated with addresses at which each record is stored. Character strings in full-text searches can also be treated as index keys.
Because the index keys can be expressed as bit strings, the searching of a database is equivalent to searching for bit strings in the database.
In order to perform the above-noted searching for bit strings at high speed, conventional art makes various refinements on the data structure in which bit strings are stored. One of these is a tree structure known as a Patricia tree.
FIG. 1 shows an example of a Patricia tree used for search processing in the above-noted conventional art. A node of a Patricia tree is formed to include an index key, a test bit position for a search key, and right and left link pointers. Although it is not explicitly shown, a node of course includes information for the purpose of accessing a record corresponding to the index key.
In the example shown in FIG. 1, the node 1750a that holds the index key “100010” is a root node, the test bit position 1730a of which is 0. The node 1750b is connected to the left link 1740a of the node 1750a, and the node 1750f is connected to the right link 1741a of the node 1750a. 
The index key held by the node 1750b is “010011”, and the test bit position 1730b is 1. The node 1750c is connected to the left link 1740b of the node 1750b, and the node 1750d is connected to the right link 1741b of the node 1750b. The index key held by the node 1750c is “000111”, and the test bit position is 3. The index key held by the node 1750d is “011010”, and the test bit position is 2.
The parts connected to the node 1750c by a solid lines show the right and left link pointers of the node 1750c, and the left pointer 1740c that is not connected by the dotted line indicates that field is blank. The dotted line connection destination of the right pointer 1741c that is connected by a dotted line expresses the address indicated by the pointer, and in this case this indicates that the right pointer points to the node 1750c. 
The right pointer 1741d of the node 1750d points to the node 1750d itself, and the node 1750e is connected to the left link 1740d. The index key held by 1750e is “010010”, and the test bit position is 5. The left pointer 1740e of the node 1750e points to the node 1750b, and the right pointer 1741e of the node 1750e points to the node 1750e. 
The index key held by the node 1750f is “101011”, and the test bit position 1730f is 2. The node 1750g is connected to the left link 1740f of the node 1750f and the node 1750h is connected to the right link 1741f of the node 1750f. 
The index key held by the node 1750g is “100011”, and the test bit position 1730g is 5. The left pointer 1740g of the node 1750g points to the node 1750a, and the right pointer 1741g of the node 1750g points to the node 1750g. 
The index key held by the node 1750h is “101100”, and the test bit position 1730h is 3. The left pointer 1740h of the node 1750h points to the node 1750f, and the right pointer 1741h of the node 1750h points to the node 1750h. 
In the example of FIG. 1, the configuration is such that, as the tree is traversed downward from the root node 1750a the test bit position of successive nodes increases. When a search is performed with some search key, the search keys' bit values corresponding to test bit positions held in nodes are successively tested from the root node, and a judgment is made as to whether the bit value at a test bit position is 1 or 0, the right link being followed if the bit value is 1, and the left link being followed if the bit value is 0. Unless the test bit position of a link target node is larger than the bit position of the link origin node, that is, if the link target is not below but rather returns upward (the returning links shown by the dotted lines in FIG. 1 being called back links), a comparison is performed between the index key of the link target and the search key. It is assured that if the result of the comparison is that the values are equal the search succeeds, but if the result is non-equal, the search fails.
As described above, although search processing using a Patricia tree has the advantages of being able to perform a search by testing only the required bits, and of it only being necessary to perform an overall key comparison one time, there are the disadvantages of an increase in storage capacity caused by the inevitable two links from each node, the added complexity of the decision processing because of the existence of back links, delay in the search processing by comparison with an index key for the first time by returning by a back link, and the difficulty of data maintenance such as adding and deleting a node.
In order to resolve these disadvantages of the Patricia tree, there is, for example, the technology disclosed in Patent Reference 1 below. In the Patricia tree described in Patent Reference 1 below, by storing lower level sibling nodes in a contiguous area, the space need for pointers is reduced as well as by setting a bit in each node to show whether or not the next link is a back link the determination processing for back links is reduced.
However, even in the disclosure of Patent Reference 1 below, since each node always reserves an area for the index key and the area for a pointer, and a single pointer is used for storing lower level sibling nodes in a contiguous area as shown for example even in the parts of left pointer 1740c, right pointer 1741h, etc. that are the lowest level parts of the Patricia shown in FIG. 1, the same amount of space must be allocated, etc., and there is not a very big space reduction effect. Also the problem of the delay in the search processing caused by a back links, and the difficulty of processing such as adding and deleting, etc., is not improved.
On one hand, there are cases in the processing of bit strings where some of the bits should be treated as non-significant “don't care” bits. For example, in searching a routing table in a router, it is preferable to treat the network address part as significant bits and the host address part as “don't care” bits in the bit string expressing an IP (Internet Protocol) address.
Patent Reference 2 recites an art of a longest-match search circuit for speeding up a longest-match search method using a Patricia tree and illustrates the correspondence relationship between nodes in a Patricia tree and bit strings that have “don't-care” bits. Also Patent Reference 2 recites an art of applying that longest-match search circuit to a routing table search system.
On the other hand, not only IP addresses, but also all kinds of classification codes support bit strings that express both individual bit string values and the contents of a hierarchical classification expressed in that bit string, and the higher the order of the bits the higher the hierarchical level they express. In searches for this kind of a bit string, cases exist wherein searches are performed with a bit string where the search key has a lower order part of bits as “don't care” bits”.
This is due to the fact that it is desirable to know whether or not an index key exists with the classification associated with that of the bit string specified as the search key, and if none such exists, to know the lowest order classification among the higher level classifications associated with the bit string specified as the search key, in other words, to know what classification is the closest to that expressed in the search key.
In this way, it is desirable to perform a longest-match search while considering don't-care bits. Also, even in functions such as ordinary character string searches, there are demands for the realization of flexible searches by means of searches that allow don't-care bits to be included in both the bit strings used as search keys and the index keys that are the object of searches.
Still, the previous means for speeding up a longest-match search have required cumbersome preprocessing and have a high cost for data maintenance. No means is known that satisfies all the requirements that a longest-match search taking in account don't-care bits exists, that the search is high speed, and that the maintenance costs are low.
For example, in the IP address search table creation method recited in Patent Reference 3, in the case wherein the range of the IP addresses for the first entry are included in the range of the IP addresses for the second entry, the first entry is decomposed into the third and fourth entries that comprise the first entry and the first entry is deleted. Then, the third and the fourth entries are each compared with the second entry and the decomposed entry that matches is deleted.
The decomposition repeatedly expands the range of “1's” in the value of the subnet mask one at a time until the decomposed entry coincides with the second entry. Since the inclusion relationship between the two entries is dissolved by the decomposition, a hardware based high-speed search appliance can consistently enable the execution of a correct longest-match search. However, since the inclusion relationship changes whenever an entry is added or deleted, the cost of data maintenance is high.
Also Patent Reference 4 recites a method for speeding up a longest-match search of things like a word dictionary in natural language processing. This method first sorts the record groups in ascending order according to a key item (words registered in a dictionary). Then, for each record, in the records preceding that record, the number of the record holding a key item that is a longest-match with the key of the given record is set as a “Next Pointer”.
When using a dictionary wherein this kind of a “Next Pointer” is set, a binary search is performed using a search key word and the key item in the record that is the search result is compared with the search key word and if there is non-coincidence, by successively traversing the Next Pointers, a longest-match search is enabled. This method utilizes the high speed of a binary search and enables a longest-match search. However the record numbers and next pointers have to be reset whenever a record is added or deleted.    Patent Document 1: Japanese Published Patent Application 2001-357070    Patent Document 2: Japanese Published Patent Application 2003-224581    Patent Document 3: Japanese Published Patent Application 1999-103318    Patent Document 4: Japanese Published Patent Application 1998-177582